#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param A: an integer sorted array
    @param target: an integer to be inserted
    @return: a list of length 2, [index1, index2]
    """
    def searchRange(self, A, target):
        if not A: return -1, -1

        left, right = 0, len(A) - 1

        while left <= right:
            medium = (left + right) // 2
            med_v = A[medium]
            if target == med_v:
                break

            if target > med_v:
                left = medium + 1
            else:
                right = medium - 1

        if left > right:
            # (1, 1) // 2 = 1,  1 + 1= 2, 1 - 1= 0
            return -1, -1
        else:
            return self.find_left_right(A, target, medium, left, right)

    def find_left_right(self, A, target, medium, most_left, most_right):
        left, right = medium, medium

        # 这里找重复: 是线性复杂度, 能否更快些
        while left > most_left:
            if A[left-1] != target:
                break
            else:
                left -= 1

        # 这里找重复: 是线性复杂度, 能否更快些
        while right < most_right:
            if A[right+1] != target:
                break
            else:
                right += 1

        return left, right


def main():
    print("start main")
    s = Solution()
    # ret = s.searchRange([0, 3, 8, 8, 8, 9], 8)
    ret = s.searchRange([1], 1)
    print(ret)

if __name__ == "__main__":
    main()
